package dataStructure.chapter01_复杂度;

/**
 * @author https://gitee.com/W_Jun
 * @date 2022-01-13 15:03
 * @Description  0, 1, 1, 2, 3, 5, 8, 13，...是斐波那契数列。
 *              求第n项的数是多少？
 *              (n从0开始，比如第0位是0，第1位是1，第2位是1，第3位是2...)
 */
public class Fibonacci {
    public static void main(String[] args) {
        //注意：因为我这里代码实现用的是int型，而当n=47时，就会出现结果为负，明显是超出了int的范围（2147483647）
        //所以我们规定，测试的n最大不能超出46.
        int n = 46;
        long start = System.currentTimeMillis();
        System.out.println(fib1(n));
        long end = System.currentTimeMillis();
        long spentTime = end - start;
        System.out.println("递归求斐波那契数列第"+ n +"位，耗时：" + spentTime + "ms");
        start = System.currentTimeMillis();
        System.out.println(fib2(n));
        end = System.currentTimeMillis();
        spentTime = end - start;
        System.out.println("迭代求斐波那契数列第"+ n +"位，耗时：" + spentTime + "ms");
    }
    //解法一：递归。第n位上的数是第n-1位和第n-2位的数之和。
    //时间复杂度O(2^N)
    public static int fib1(int n) {
        if (n <= 1) return n;
        return fib1(n - 1) + fib1(n - 2);
    }
    //解法二：迭代。
    // 第n位上的数的计算，每次都是它前边的两个数之和，进一步考虑最初的(0和1)两个数的累加，从它们开始，
    // 不断将最初的两个数迭代（用它们中的第二个数变为下一次的第一个数，用累加结果作为下一次的第二个数）
    // 最终的结果sum被保存在了second中。需要知道循环了n-1次
    //时间复杂度O(N)
    public static int fib2(int n) {
        if (n <= 1) return n;
        int first = 0;
        int second = 1;
        for (int i = 0; i < n - 1; i++) {
            int sum = first + second;
            first = second;
            second = sum;
        }
        return second;
    }
}
